// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func interpolationSearch(array []int, key int) int {
	min, max := array[0], array[len(array)-1]

	low, high := 0, len(array)-1

	for {
		if key < min {
			return low
		}

		if key > max {
			return high + 1
		}

		// 猜测位置
		var guess int
		if high == low {
			guess = high
		} else {
			size := high - low
			offset := int(float64(size-1) * (float64(key-min) / float64(max-min)))
			guess = low + offset
		}

		if array[guess] == key {
			// 向后扫描值范围的开始
			for guess > 0 && array[guess-1] == key {
				guess--
			}
			return guess
		}

		// 如果我们猜高，则猜低，反之亦然
		if array[guess] > key {
			high = guess - 1
			max = array[high]
		} else {
			low = guess + 1
			min = array[low]
		}
	}
}

func main() {
	arr := []int{1, 6, 8, 22, 23, 33, 55, 66, 99}
	res := interpolationSearch(arr, 33)
	fmt.Println(res)
}

//$ go run interpolationSearch.go
//5
